package com.learn.algorithm.string;

public class KMP {

    public static int[] getNext(char[] target) {
        int length = target.length;
        if (length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < length) {
            if (target[i - 1] == target[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }

    public static int kmp(char[] source, char[] target) {
        int x = 0, y = 0;
        int m = source.length;
        int n = target.length;
        int[] next = getNext(target);
        while (x < m && y < n) {
            if (source[x] == target[y]) {
                x++;
                y++;
            } else if (y > 0) {
                y = next[y];
            } else {
                x++;
            }
        }
        return y == n ? x - y : -1;
    }

    public static void main(String[] args) {
        System.out.println(kmp("abcabcabct".toCharArray(), "abct".toCharArray()));
    }
}
